package 层序遍历;

import java.util.*;

/**
 * @Date 2024/9/8 22:29
 * @description: N叉树的锯齿状层序遍历
 * .    https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
 * @Author LittleNight
 */
public class TreeNode {

    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }

    // 练习
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return new ArrayList<>();
        // 创建一个队列. 双向链表做队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int flag = 0;
        // 层序遍历主逻辑
        while(!queue.isEmpty()) {
            flag++;
            int sz = queue.size();
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < sz; i++) {
                // 弹出队列元素, 加入到结果中, 并把孩子节点加入到队列中
                TreeNode node = queue.poll();
                tmp.add(node.val);
                // 加入左右孩子节点
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            // 加入之前判断是否需要翻转
            if(flag % 2 == 0) Collections.reverse(tmp); // 翻转列表list
            ret.add(tmp);
        }
        return ret;


    }

}
